package com.zang.greedy;

import java.util.Arrays;

/**
 * @author ZVerify
 * @since 2022/11/22 21:04
 **/
public class 用最少数量的箭引爆气球 {
    public int findMinArrowShots(int[][] points) {
        // 根据气球直径的开始坐标从小到大排序
        // 使用Integer内置比较方法，不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        // 不为空肯定最少要1支箭
        int count = 1;

        for (int i = 1; i < points.length; i++) {
            // 看当前的气球最左边缘和上一个使用了箭的气球边缘是否大于上一个
            // 如果大于的话肯定要需要一支新的箭
            if (points[i][0]  > points[i-1][1]) {
                count++;
            }else {
                // 如果小于的话拿到当前的气球和上一个气球的最右边的最小值，
                // 因为如果小于最小值的话肯定小于所有的就可以还用上一支箭
                points[i][1] = Math.min(points[i][1],points[i-1][1]);
            }
        }
        return count;
    }
}
